package cn.arnold.leetcode;

/**
 * @Author Arnold
 * @Desc 数组中第K大的值：快排
 **/
public class QuickSortPartition {

    public static int findTarget(int[] nums, int k) {
        int left = 0;
        int right = nums.length - 1;
        int target = nums.length - k;
        while (true) {
            int index = partition(nums, left, right);
            if (index == target) {
                return nums[index];
            } else if (index < target) {
                left = index + 1;
            } else {
                right = index - 1;
            }
        }
    }

    /**
     * 每一次切分后，基准元素都呆在它该呆的位置（左边的数都小于它，右边的数都大于它）
     *
     * @param nums
     * @param left
     * @param right
     * @return 基准元素被切分后在数组中的索引
     */
    public static int partition(int[] nums, int left, int right) {
        int pivot = nums[left];
        int j = left;
        for (int i = left + 1; i <= right; i++) {
            if (nums[i] < pivot) {
                // 小于 pivot 的元素都被交换到前面
                j++;
                swap(nums, j, i);
            }
        }
        // 在之前遍历的过程中，满足 [left + 1, j] < pivot，并且 (j, i] >= pivot
        swap(nums, j, left);
        return j;
    }

    public static void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}
